#include <iostream>
#include <vector>
#include <queue>

using namespace std;
// 102.二叉树的层序遍历
// 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == nullptr)
            return res;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;

            for(int i = 0; i < levelSize; i++) {
                TreeNode *currNode = q.front();
                q.pop();
                currentLevel.push_back(currNode->val);

                if(currNode->left)
                    q.push(currNode->left);
                if(currNode->right)
                    q.push(currNode->right);
            }
            res.push_back(currentLevel);
        }
        return res;
    }
};

void printRes(vector<vector<int>>& res) {
    cout << "[";
    for(int i = 0; i < res.size(); i++) {
        cout << "[";
        for(int j = 0; j < res[i].size(); j++) {
            cout << res[i][j];
            if(j < res[i].size() - 1)
                cout << ",";
        }
        cout << "]";
        if(i < res.size() - 1)
            cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    TreeNode* root1 = new TreeNode(3,new TreeNode(9),new TreeNode(20,
                                                                  new TreeNode(15),new TreeNode(7)));
    vector<vector<int>> res1 = Solution().levelOrder(root1);
    printRes(res1);
    return 0;
}
